#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

#include "graph.h"

Graph::Graph()
{
    _afD=NULL;
    _anParent=NULL;
    //_aanParent=NULL;
    _nLength=0;
    _Knots = NULL;
    _knotsWhereIveBeen = NULL;
    _nLastLength=-1;
}

Graph::Graph(const Knots* structure, int n)
{
    _nLastLength=-1;

    InitWithData(structure, n);
}

void Graph::InitWithData(const Knots* structure, int n)
{
    if( _Knots != NULL)
        free(_Knots);

    _Knots=(Knots*)malloc(sizeof(Knots)*n);
    for(int i=0; i<n; i++)
    {
        _Knots[i]._nKnot=structure[i]._nKnot;
        _Knots[i]._aWhereToGo=structure[i]._aWhereToGo;
        _Knots[i]._nCountWhere=structure[i]._nCountWhere;
    }
    _nLastLength=_nLength;
    _nLength=n;
    commonInit();
}

void Graph:: ReInitWithoutDeletion(Knots* structure, int n)
{
    assert(structure!=NULL);
    _Knots = structure;

    _nLength=n;

    commonInit();
}

void Graph:: commonInit()
{
    // structure initialization
    if(_anParent!=NULL)
        free(_anParent);

    _anParent=(int*)malloc(sizeof(int)*_nLength);

    if(_afD!=NULL)
	free(_afD);
    _afD=(int*)malloc(sizeof(int)*_nLength);

    /*
    if(_aanParent!=NULL && _nLastLength!=_nLength)
    {
	for(int i=0; i<COPY_COUNTS; i++)
	    free(_aanParent[i]);
	free(_aanParent);
	_aanParent=NULL;
    }
    */

    _knotsWhereIveBeen=NULL;
    // you have to set up this data manually;
    _anLinesOfNodes=NULL;
    _anCurLineNodeNumbers=NULL;
    _anNumbersOfLinesUsed=NULL;
    _anNumbersNextToUse=NULL;
}

void Graph::distancesInit()
{
    if(!_nLength)
	return;

    for(int i=0; i<_nLength; i++)
    {
	_anParent[i]=Nill;
	_afD[i]=Infinity;
    }
    _afD[_nStart]=0;
}

#ifdef DEBUG_G
int nRelax=0;
#endif

// as a condition u and v must be less then _nLength!
// for speedness I do not test this condition!
void Graph::relax(int u, int v, int weight)
{
#ifdef DEBUG_G
    if(u<0 || u>=_nLength)
    {
        //fprintf(stderr, "relax: error, u should be positive and less than array's length!\n");
	return;
    }
     if(v<0 || v>=_nLength)
     {
        //fprintf(stderr, "relax: error, v should be positive and less than array's length!\n");
	return;
     }
     if(weight<0)
         fprintf(stderr, "relax: error, weight must be positive!\n");

nRelax++;
#endif

    if(_afD[u]>_afD[v]+weight)
    {
	_afD[u]=_afD[v]+weight;
	_anParent[u]=v;
    }
}

void Graph:: setInfoAboutLineNums(int* info)
{
    // the size must be equal to _nLength!!!
    // how to prove it I do not know!
    _anLinesOfNodes=info;    
}

int Graph::getWeight(int node)
{
	return _afD[node];	
}

// cyclon-B algorithm
// 26.10.2009
void Graph:: applyCyclon()
{
    assert(_anLinesOfNodes!=NULL);
    int nCurLine=_anLinesOfNodes[_nStart];
    // start with fresh data:
    if(_anNumbersNextToUse==NULL)
	_anNumbersNextToUse=new Queue();
    else
	_anNumbersNextToUse->deleteAll();
    //next initialize the numbers of lines we've been...
    if(_anNumbersOfLinesUsed==NULL)
	_anNumbersOfLinesUsed=new Queue();
    else
	_anNumbersOfLinesUsed->deleteAll();
    // initialize the queque to proceed the nodes on the current line:
    if(_anCurLineNodeNumbers==NULL)
	_anCurLineNodeNumbers=new Queue();
    else
	_anCurLineNodeNumbers->deleteAll();
    if(_knotsWhereIveBeen==NULL)
	_knotsWhereIveBeen=new Queue();
    else
	_knotsWhereIveBeen->deleteAll();
    
    int nCurNode=_nStart;

    // we'll exit from the cycle by our own means see condition below:
    for(;;){
	for(int i=0; i<_Knots[nCurNode]._nCountWhere; i++)
	{
	    int nNode=_Knots[nCurNode]._aWhereToGo[i].knot;
	    // relax the node:
	    relax(nCurNode, _Knots[nCurNode]._aWhereToGo[i].knot, 
		    _Knots[nCurNode]._aWhereToGo[i].weight);

	    if(_anLinesOfNodes[nNode]==nCurLine)
	    {
		// initiate relaxating procedure and add 
		// node to the queue for next proceeding:
		_anCurLineNodeNumbers->enqueue(_Knots[nCurNode]._aWhereToGo[i].knot);
	    }
	    else
	    {
		// else add the node to another queue for other lines
		_anNumbersNextToUse->enqueue(_Knots[nCurNode]._aWhereToGo[i].knot);
	    }
	}
	//add current number to the used elements:
	_knotsWhereIveBeen->enqueue(nCurNode);
	// if we've got more elements to proceed on the current line
	// dequeue it:
	bool bFound;
	do{
	    bFound=false;
	    if(_anCurLineNodeNumbers->size()==0)
		break;
	    nCurNode=_anCurLineNodeNumbers->dequeue();
	    bFound=true;
	}
	while(_knotsWhereIveBeen->doesContain(nCurNode)); // we've been there before..

	// change current line:
	if(!bFound)
	{
	    // try to find another node on the other line, where we were not:
	    do{
		bFound=false;
		if(_anNumbersNextToUse->size()==0)
		    break;
		nCurNode=_anNumbersNextToUse->dequeue();
		bFound=true;
	    }
	    while(_knotsWhereIveBeen->doesContain(nCurNode)); // we've been there before..
	    // we've not been there, use that line
	    if(bFound)
		nCurLine=_anLinesOfNodes[nCurNode];
	    else
		break; // there are no more lines, where we were not.
	    		// exit...
	}
    }
}

void Graph:: applyCyclonC(int* allowedLineNumbers, int nAllowedCount)
{
    assert(_anLinesOfNodes!=NULL);
    for(int i=0; i<nAllowedCount; i++)
	printf("Allowed line: %d;\n", allowedLineNumbers[i]);

    for(int i=0; i<_nLength; i++){
	_afD[i]=Infinity;
	_anParent[i]=Nill;
    }
    setStart(_nStart);

    // then inialize our additional structs for getting information about
    // history later:
    // for Modification of the Cyclon-B with limited numbers of lines:
    // 2.11.2009 I do not want to use so much memory... so I'd 
    // loose that amount of it:
    /*
    if(_aanParent==NULL){
	_aanParent=(int**)malloc(sizeof(int)*COPY_COUNTS);
	_nOtherWaysCount=0;
	for(int i=0; i<COPY_COUNTS; i++)
	    _aanParent[i]=(int*)malloc(sizeof(int)*_nLength);
    }
    */
    int nCurLine=_anLinesOfNodes[_nStart];
    // start with fresh data:
    if(_anNumbersNextToUse==NULL)
	_anNumbersNextToUse=new Queue();
    else
	_anNumbersNextToUse->deleteAll();
    //next initialize the numbers of lines we've been...
    if(_anNumbersOfLinesUsed==NULL)
	_anNumbersOfLinesUsed=new Queue();
    else
	_anNumbersOfLinesUsed->deleteAll();
    // initialize the queque to proceed the nodes on the current line:
    if(_anCurLineNodeNumbers==NULL)
	_anCurLineNodeNumbers=new Queue();
    else
	_anCurLineNodeNumbers->deleteAll();
    if(_knotsWhereIveBeen==NULL)
	_knotsWhereIveBeen=new Queue();
    else
	_knotsWhereIveBeen->deleteAll();
    
    int nCurNode=_nStart;

    // we'll exit from the cycle by our own means see condition below:
    for(;;){
	for(int i=0; i<_Knots[nCurNode]._nCountWhere; i++)
	{
	    int nNode=_Knots[nCurNode]._aWhereToGo[i].knot;
	    // relax the node:
	    relax(nCurNode, _Knots[nCurNode]._aWhereToGo[i].knot, 
		    _Knots[nCurNode]._aWhereToGo[i].weight);

	    if(_anLinesOfNodes[nNode]==nCurLine)
	    {
		// initiate relaxating procedure and add 
		// node to the queue for next proceeding:
		_anCurLineNodeNumbers->enqueue(_Knots[nCurNode]._aWhereToGo[i].knot);
	    }
	    else
	    {
		// else add the node to another queue for other lines
		/*
		printf("Adding node from another line: %d; with line num: %d\n", 
			_Knots[nCurNode]._aWhereToGo[i].knot,
			_anLinesOfNodes[_Knots[nCurNode]._aWhereToGo[i].knot]);
			*/
		_anNumbersNextToUse->enqueue(_Knots[nCurNode]._aWhereToGo[i].knot);
	    }
	}
	//add current number to the used elements:
	_knotsWhereIveBeen->enqueue(nCurNode);
	// if we've got more elements to proceed on the current line
	// dequeue it:
	bool bFound;
	do{
	    bFound=false;
	    if(_anCurLineNodeNumbers->size()==0)
		break;
	    nCurNode=_anCurLineNodeNumbers->dequeue();
	    bFound=true;
	}
	while(_knotsWhereIveBeen->doesContain(nCurNode)); // we've been there before..

	// change current line:
	if(!bFound)
	{
	    // try to find another node on the other line, where we were not:
	    do{
		bFound=false;
		if(_anNumbersNextToUse->size()==0)
		    break;
		nCurNode=_anNumbersNextToUse->dequeue();
		/*
		printf("node from another line  %d; its line number: %d\n", nCurNode, 
			_anLinesOfNodes[nCurNode]);
			*/
		// then check if the node lays on the allowed line:
		bool bAllowed=false;
		for(int j=0; j<nAllowedCount; j++)
		    if(allowedLineNumbers[j]==_anLinesOfNodes[nCurNode])
			bAllowed=true;
		if(!bAllowed){
		    // set the node from the used list:
		    nCurNode=_knotsWhereIveBeen->get(0);
		    continue; // the node shouldn't be used!
		}
		bFound=true;
	    }
	    while(_knotsWhereIveBeen->doesContain(nCurNode)); // we've been there before..
	    // we've not been there, use that line
	    if(bFound)
		nCurLine=_anLinesOfNodes[nCurNode];
	    else
		break; // there are no more lines, where we were not.
	    		// exit...
	}
    }
    // you should think about using parts of old algorithm...
    // and make the copy of what we've gone through, please:
    //printWeights();
    //makeACopyOfParents();
}

// 2.11.2009 CyclonB uses only one line, so doesn't need
// info about line numbers of nodes:
void Graph:: applyCyclonB()
{
    // start with fresh data:
    if(_anNumbersNextToUse==NULL)
	_anNumbersNextToUse=new Queue();
    else
	_anNumbersNextToUse->deleteAll();

    if(_knotsWhereIveBeen==NULL)
	_knotsWhereIveBeen=new Queue();
    else
	_knotsWhereIveBeen->deleteAll();
    
    int nCurNode=_nStart;

    // we'll exit from the cycle by our own means see condition below:
    for(;;){
	for(int i=0; i<_Knots[nCurNode]._nCountWhere; i++)
	{
	    // relax the node:
	    relax(nCurNode, _Knots[nCurNode]._aWhereToGo[i].knot, 
		    _Knots[nCurNode]._aWhereToGo[i].weight);

	    // add the node to a queue for postprocessing:
	    _anNumbersNextToUse->enqueue(_Knots[nCurNode]._aWhereToGo[i].knot);
	}
	//add current number to the used elements:
	_knotsWhereIveBeen->enqueue(nCurNode);
	// if we've got more elements to proceed on the current line
	// dequeue it:
	bool bFound;
	do{
	    bFound=false;
	    if(_anNumbersNextToUse->size()==0)
		break;
	    nCurNode=_anNumbersNextToUse->dequeue();
	    bFound=true;
	}
	while(_knotsWhereIveBeen->doesContain(nCurNode)); // we've been there before..

	if(!bFound)
	    break; // end of our algorithm;

    }
}


// REMARK: the algorithm is too slow to use in the real-time app; try Dejkstra instead
// the practise said, on the real structure of stations the algorithm was even faster
// then Dejkstra (but I know the realisation of it was made by my bad hands)

// correction to original algorithm:
// 10.08.09 if the distance to any knot equals Infinity
// than we need to add that knot into recalculation circle... 
void Graph::applyBellmanFord()
{
    int toRecalc[_nLength];
    int n=0;
    for(int i=0; i<_nLength; i++)
    {
	for(int j=0; j<_Knots[i]._nCountWhere; j++)
	    relax(i, _Knots[i]._aWhereToGo[j].knot, _Knots[i]._aWhereToGo[j].weight);
	if(_afD[i]== Infinity)
	    toRecalc[n++]=i;
    }
#ifdef DEBUG_G
fprintf(stderr, "The count of relaxations (before recalculation): %d\n", nRelax);
#endif
    // correction to original algorithm:
    while(n){
	int len=n;
#ifdef DEBUG_G
	    fprintf(stderr, "Stations left to recalculate\n");
	    for(int mm=0; mm<len; mm++)
		fprintf(stderr, "%d\n", toRecalc[mm]);
	    fprintf(stderr, "----------------------------\n");
#endif

	n=0;
	for(int k=0; k<len; k++)
        {
            int i=toRecalc[k];
	    for(int j=0; j<_Knots[i]._nCountWhere; j++)
		relax(i, _Knots[i]._aWhereToGo[j].knot, _Knots[i]._aWhereToGo[j].weight);
	    if(_afD[i]== Infinity)
		toRecalc[n++]=i;
	}
    }
#ifdef DEBUG_G
fprintf(stderr, "The count of relaxations (after recalculation): %d\n", nRelax);
#endif
}

void Graph::applyDejkstra()
{
    int *anKnots=(int*)malloc(sizeof(int)*_nLength);
    int i;
    int nS=0;
    for(i=0; i<_nLength; i++){
        if(_Knots[i]._nKnot==_nStart)continue;
        anKnots[nS++]=_Knots[i]._nKnot;
    }

    // an array with all knots available to us:
    queue.initWithData(anKnots, _nLength-1);
    // the links to other knots in the tree:
    queue.setKnots(_Knots, _nLength);
    free(anKnots);

    // start out algorithm:
    queue.setMinExtr(_nStart);
#ifdef DEBUG_SHOW_QUEUE
    int iter=0;
#endif

    while(queue.areThereMoreElements())
    {
#ifdef DEBUG_SHOW_QUEUE
        fprintf(stderr, "Iteraction: %d\n", iter);
        queue.printContents();
        iter++;
#endif
	int nKnot=queue.extract_min();
	// find knot's relatives knots:
	for(i=0; i<_nLength; i++)
	    if(nKnot==_Knots[i]._nKnot)
		break;
	for(int j=0; j<_Knots[i]._nCountWhere; j++)
	    relax(i, _Knots[i]._aWhereToGo[j].knot, _Knots[i]._aWhereToGo[j].weight);
    }
}

/*
int* Graph:: getPrevCopyOfParents()
{
    assert(_nCurPointerToParent>=0);
    if(_nCurPointerToParent+1>=_nOtherWaysCount)
	return NULL;
    return _aanParent[_nCurPointerToParent++];
}

int* Graph:: getNextCopyOfParents()
{
    assert(_nCurPointerToParent>=0);
    if(_nCurPointerToParent-1<0)
	return NULL;
    return _aanParent[_nCurPointerToParent];
}

bool Graph:: areWeAtTheStartOrEnd()
{
    if(_nCurPointerToParent==0 || 
	    _nCurPointerToParent==_nOtherWaysCount-1)
	return true;
    return false;
}

void Graph:: deleteAllParentsHistory()
{
    _nCurPointerToParent=0;
    _nOtherWaysCount=0;
}
*/

/*
void Graph:: makeACopyOfParents()
{
    //printf( "Making a copy of our parents!\n");
    if(_nOtherWaysCount<COPY_COUNTS)
	memcpy(_aanParent[_nOtherWaysCount++], _anParent, sizeof(int)*_nLength);
}
*/
/*
 * Gets parent of the variable node
 */
int Graph::getParent(int node)
{
    return _anParent[node];
}

void Graph::printParents()
{
    for(int i=0; i<_nLength; i++)
        fprintf(stderr, "Knot %d, Parent: %d\n", i, _anParent[i]);
}

void Graph::printWeights()
{
    for(int i=0; i<_nLength; i++)
        fprintf(stderr, "Knot %d, Weight: %d\n", i, _afD[i]);

#ifdef DEBUG_G
fprintf(stderr, "The count of relaxations: %d\n", nRelax);
#endif
}

void Graph::setStart(int n)
{
    _nStart=n;
    distancesInit();
}

Graph::~Graph(){

    if(_afD != NULL)
	delete _afD;

    if(_anParent != NULL)
	delete _anParent;

    if(_nLength!=0)
    {
	for(int i=0; i<_nLength; i++)
	    free(_Knots[i]._aWhereToGo);
	free(_Knots);
    }

    if(_anNumbersNextToUse!=NULL)
	delete _anNumbersNextToUse;
    
    if(_anNumbersOfLinesUsed!=NULL)
	delete _anNumbersOfLinesUsed;

    if(_anCurLineNodeNumbers!=NULL)
	delete _anCurLineNodeNumbers;

    if(_knotsWhereIveBeen!=NULL)
	delete _knotsWhereIveBeen;
   
    /*
    if(_nOtherWaysCount)
    {
	for(int i=0; i<_nOtherWaysCount; i++)
	    free(_aanParent[i]);
    }
    free(_aanParent);
    */
}
